// 归并排序
const arr = [5, 3, 4, 1, 2, 8, 7, 6, 9, 0];

// 将数组arr排序
const merge_sort = (arr, l, r) => {
  //当只有一个元素时，看作是排好序的数组
  if (l >= r) return;

  // 分成两个子任务
  let mid = (l + r) >> 1;
  merge_sort(arr, l, mid); // 左边进行排序
  merge_sort(arr, mid + 1, r); // 右边进行排序

  // 合并排好序的左右结果，得到排好序的大任务
  let p1 = l, // 左序列开始下标
    p2 = mid + 1, // 右序列开始下标
    tem = [], // 额外空间
    k = 0; // 额外空间尾部下标

  while (p1 <= mid || p2 <= r) {
    // 将左区间元素放入额外空间: 右区间无元素，或者左区间元素小于右区间元素
    if ((p2 > r) || (p1 <= mid && arr[p1] <= arr[p2])) {
      tem[k] = arr[p1++];
    } else {
      tem[k] = arr[p2++];
    }
    k++;
  }
  // 将额外空间元素拷贝回原数组
  for (let i = l; i <= r; i++) {
    arr[i] = tem[i - l];
  }
}

merge_sort(arr, 0, arr.length - 1)
console.log(arr);